package com.itheima.DSA;

/**
 * @author ZhouYu
 * @version 1.0
 */
public class BinarySearch {

    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        System.out.println(binarySearch(a, 5));
    }

    /**
     * 二分查找基础版
     *
     * @param a      - 待查找的升序数组
     * @param target - 待查找的目标值
     * @return 找到则返回索引
     * 找不到返回-1
     */
    public static int binarySearch(int[] a, int target) {
        int left = 0, right = a.length - 1; //设置指针和初始值
        while (left <= right) { // 范围有东西
            int mid = (left + right) >>> 1;
            if (target < a[mid]) { // 目标在左边
                right = mid - 1;
            } else if (target > a[mid]) { // 目标在右边
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
    /*
    问题一：为什么是 left <= right 意味着区间内有未比较的元素，而不是 left < right？
           left == right 意味着 left，right 它们指向的元素也会参与比较
           left < right 只意味着 m 指向的元素参与比较
    问题二：(left+right) / 2 有没有问题？
    问题三：都写成小于号有啥好处？
     */


    /*
      1  [2,3,4,5] 5 右侧没找到更差
      int left = 0, right = a.length;    2
      return -1                          1
      元素个数                循环次数
      4-7                        3        floor(log_2(4)) = 2+1   向下取整
      8-15                       4             log_2(8) = 3+1
      16-31                      5             log_2(16) = 4+1
      32-63                      6             log_2(32) = 5+1
       ...                      ...            log_2(n)+1

      循环次数L ：floor(log_2(n)) + 1


      left <= right                      L+1
      int mid = (left + right) >>> 1;    L
      target < a[mid]                    L
      target > a[mid]                    L
      left = mid + 1;                    L

      总共 (floor(log_2(n)) + 1) * 5 + 4
     */




    public static int binarySearchAlternative(int[] a,int target){
        int left = 0, right = a.length;       // 第一处
        while (left < right) {                // 第二处
            int mid = (left + right) >>> 1;
            if (target < a[mid]) {
                right = mid;                  // 第三处
            } else if (target > a[mid]) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }


    public static int binarySearch3(int[] a,int target){
        int left = 0, right = a.length;
        while (1 < right-left){
            int mid = (left+right) >>> 1;
            if (target < a[mid]){
                right = mid;
            }else {
                left = mid;
            }
        }
        if (a[left] == target){
            return left;
        }else {
            return -1;
        }
    }

    /**
     * 找到最左边的target
     * @param a
     * @param target
     * @return
     */
    public static int binarySearchLeftmost1(int[] a,int target){
        int left = 0, right = a.length - 1;
        int candidate = -1;
        while (left <= right) {
            int mid = (left + right) >>> 1;
            if (target < a[mid]) {
                right = mid - 1;
            } else if (target > a[mid]) {
                left = mid + 1;
            } else {
                // 记录候选位置
                candidate = mid;
                right = mid - 1;
            }
        }
        return candidate;
    }

    public static int binarySearchRightmost1(int[] a,int target){
        int left = 0, right = a.length - 1;
        int candidate = -1;
        while (left <= right) {
            int mid = (left + right) >>> 1;
            if (target < a[mid]) {
                right = mid - 1;
            } else if (target > a[mid]) {
                left = mid + 1;
            } else {
                // 记录候选位置
                candidate = mid;
                left = mid + 1;
            }
        }
        return candidate;
    }

    public static int binarySearchLeftmost2(int[] a,int target){
        int left = 0, right = a.length - 1;
        while (left <= right) {
            int mid = (left + right) >>> 1;
            if (target <= a[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    public static int binarySearchRightmost2(int[] a,int target){
        int left = 0, right = a.length - 1;
        while (left <= right) {
            int mid = (left + right) >>> 1;
            if (target < a[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left -1;
    }

}
